﻿#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include<stdlib.h>
int main()
{
    printf("hello world\n");
    system("pause");
    return 0;
}



//
//力扣 647. 回文子串
//class Solution {
//public:
//    int countSubstrings(string s) {
//        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
//        int result = 0;
//        for (int i = s.size() - 1; i >= 0; i--)
//        {  // 注意遍历顺序
//            for (int j = i; j < s.size(); j++)
//            {
//                if (s[i] == s[j])
//                {
//                    if (j - i <= 1)
//                    { // 情况一 和 情况二
//                        result++;
//                        dp[i][j] = true;
//                    }
//                    else if (dp[i + 1][j - 1])
//                    { // 情况三
//                        result++;
//                        dp[i][j] = true;
//                    }
//                }
//            }
//        }
//        return result;
//    }
//};
//
//
//力扣 5. 最长回文子串
//class Solution {
//public:
//    string longestPalindrome(string s) {
//        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
//        int result = 0;
//        int  len = 1;
//        int begin = 0;
//        for (int i = s.size() - 1; i >= 0; i--)
//        {  // 注意遍历顺序
//            for (int j = i; j < s.size(); j++)
//            {
//                if (s[i] == s[j])
//                {
//                    if (j - i <= 1)
//                    { // 情况一 和 情况二
//                        dp[i][j] = true;
//                    }
//                    else if (dp[i + 1][j - 1])
//                    { // 情况三
//                        dp[i][j] = true;
//                    }
//                }
//                if (dp[i][j] && j - i + 1 > len)
//                {
//                    len = j - i + 1;
//                    begin = i;
//                }
//            }
//        }
//        return s.substr(begin, len);
//    }
//};
//
//
//
//1745. 分割回文串 IV
//class Solution {
//public:
//    对于回⽂串，我们⼀般分析⼀个「区间两头」的元素：
//    /*1 . 当 s[i] != s[j] 的时候：不可能是回⽂串， dp[i][j] = 0 ；
//      2 . 当 s[i] == s[j] 的时候：根据⻓度分三种情况讨论：
//    • ⻓度为 1 ，也就是 i == j ：此时⼀定是回⽂串， dp[i][j] = true ；
//    • ⻓度为 2 ，也就是 i + 1 == j ：此时也⼀定是回⽂串， dp[i][j] = true ；
//    • ⻓度⼤于 2 ，此时要去看看 [i + 1, j - 1] 区间的⼦串是否回⽂： dp[i][j]
//    = dp[i + 1][j - 1] 。
//    综上，状态转移⽅程分情况谈论即可。*/
//    bool checkPartitioning(string s) {
//        vector<vector<bool>> dp(s.size(), vector<bool>(s.size(), false));
//
//         1. ⽤ dp 把所有的⼦串是否是回⽂预处理⼀下
//        for (int i = s.size() - 1; i >= 0; i--)
//        {  // 注意遍历顺序
//            for (int j = i; j < s.size(); j++)
//            {
//                if (s[i] == s[j])
//                {
//                    if (j - i <= 1)
//                    { // 情况一 和 情况二
//                        dp[i][j] = true;
//                    }
//                    else if (dp[i + 1][j - 1])
//                    { // 情况三
//                        dp[i][j] = true;
//                    }
//                }
//            }
//        }
//
//         2. 枚举所有的第⼆个字符串的起始位置以及结束位置
//        for (int i = 1; i < s.size() - 1; i++)
//        {
//            for (int j = i; j < s.size() - 1; j++)
//            {
//                if (dp[0][i - 1] && dp[i][j] && dp[j + 1][s.size() - 1])
//                    return true;
//            }
//        }
//
//        return false;
//
//    }
//};
//
// 力扣 单词拆分
//class Solution
//{
//public:
//    bool wordBreak(string s, vector<string>& wordDict)
//    {
//         优化⼀：将字典⾥⾯的单词存在哈希表⾥⾯
//        unordered_set<string> hash;
//        for (auto& s : wordDict) hash.insert(s);
//        int n = s.size();
//        vector<bool> dp(n + 1);
//        dp[0] = true; // 保证后续填表是正确的
//        s = ' ' + s; // 使原始字符串的下标统⼀ +1
//        for (int i = 1; i <= n; i++) // 填 dp[i]
//        {
//            for (int j = i; j >= 1; j--) //最后⼀个单词的起始位置
//            {
//                if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
//                {
//                    dp[i] = true;
//                    break; // 优化⼆
//                }
//            }
//        }
//        return dp[n];
//    }
//};
//
//
//132. 分割回文串 II
//class Solution {
//public:
//    int minCut(string s) {
//        int n = s.size();
//        vector<vector<bool>> isPal(n, vector<bool>(n)); // 统计所有⼦串是否是回⽂串
//        for (int i = n - 1; i >= 0; i--)
//        {
//            for (int j = i; j < n; j++)
//            {
//                if (s[i] == s[j])
//                {
//                    if (j - i <= 1)
//                    { // 情况一 和 情况二
//                        isPal[i][j] = true;
//                    }
//                    else if (isPal[i + 1][j - 1])
//                    { // 情况三
//                        isPal[i][j] = true;
//                    }
//                }
//            }
//        }
//        for (int i = 0; i < n; i++)
//        {
//            for (int j = 0; j < n; j++)
//            {
//                cout << isPal[i][j] << " ";
//            }
//            cout << endl;
//        }
//        cout << "dp" << endl;
//        vector<int> dp(n, INT_MAX);
//        for (int i = 0; i < n; i++)
//        {
//            if (isPal[0][i]) dp[i] = 0;
//            else
//            {
//                for (int j = 1; j <= i; j++)
//                    if (isPal[j][i])
//                    {
//                        dp[i] = min(dp[i], dp[j - 1] + 1);
//                        cout << i << endl;
//                    }
//            }
//        }
//
//        for (auto x : dp) cout << x << " ";
//        return dp[n - 1];
//    }
//};